package com.nine.algorithm.binarysearch;

/**
 * @author nine
 * @version 1.0
 * @description 二分查找
 * @date 24/4/23 21:50
 */
public class BinarySearchLeftmost {

	/**
	 * 二分查找 Rightmost2【场景：可以用来求排名】
	 *
	 * @param a      待查找的升序数组
	 * @param target 待查找的目标值
	 * @return 返回 <= target 的最靠右索引
	 */
	public static int binarySearchRightmost2(int[] a, int target) {
		int i = 0, j = a.length - 1;
		while (i <= j) {
			int m = (i + j) >>> 1;
			if (target < a[m]) {
				j = m - 1;
			}
			else {
				i = m + 1;
			}
		}
		return i - 1;
	}

	/**
	 * 二分查找 Leftmost2【场景：可以用来求排名】
	 *
	 * @param a      待查找的升序数组
	 * @param target 待查找的目标值
	 * @return 返回 >= target 的最靠左索引
	 */
	public static int binarySearchLeftmost2(int[] a, int target) {
		int i = 0, j = a.length - 1;
		while (i <= j) {
			int m = (i + j) >>> 1;
			if (target <= a[m]) {
				j = m - 1;
			}
			else {
				i = m + 1;
			}
		}
		// 返回 >= target 的最靠左索引
		return i;
	}


	/**
	 * 二分查找 Leftmost
	 *
	 * @param a      待查找的升序数组
	 * @param target 待查找的目标值
	 * @return 找到则返回最靠左索引
	 * 找不到返回 -1
	 */
	public static int binarySearchLeftmost(int[] a, int target) {
		int i = 0, j = a.length - 1;
		// 记录候选者名单
		int candidate = -1;
		while (i <= j) {
			int m = (i + j) >>> 1;
			if (target < a[m]) {
				j = m - 1;
			}
			else if (a[m] < target) {
				i = m + 1;
			}
			else if (target == a[m]) {
				// 记录候选者位置
				candidate = m;
				j = m - 1;
			}
		}
		return candidate;
	}


	/**
	 * 二分查找 Rightmost
	 *
	 * @param a      待查找的升序数组
	 * @param target 待查找的目标值
	 * @return 找到则返回最靠右索引
	 * 找不到返回 -1
	 */
	public static int binarySearchRightmost(int[] a, int target) {
		int i = 0, j = a.length - 1;
		// 记录候选者名单
		int candidate = -1;
		while (i <= j) {
			int m = (i + j) >>> 1;
			if (target < a[m]) {
				j = m - 1;
			}
			else if (a[m] < target) {
				i = m + 1;
			}
			else if (target == a[m]) {
				// 记录候选者位置
				candidate = m;
				i = m + 1;
			}
		}
		return candidate;
	}

}
